Web-based services are becoming more and more ubiquitous and in many situations, these web based services are replacing human-to-human interactions. Schemes which implicitly assume that the other party on the internet is a human, are susceptible to being deceived by programs which pretend to be humans. Such web bots generally have a malicious intent. Thus, the need to authenticate that the other party on the web-based service is a human and not a potentially malicious program is on the rise.
Human Interactive Proofs (HIPs) are schemes which require an interaction from a human user that is tough for a program to simulate. CAPTCHAs are a class of HIPs which are tests that are so designed that humans can easily pass them while machines have a very tough time passing them. In other words, a CAPTCHA is a type of challenge-response test that may be used to differentiate between human users and automated programs on the web. “CAPTCHA” is an acronym for “Completely Automated Public Turing test to tell Computers and Humans Apart”, trademarked by Carnegie Mellon University. “CAPTCHA” itself loosely means the test, the test taking process and the individual test questions comprising a test. Thus such HIPs try to prevent malicious programs while allowing humans to access the web services they are trying to secure. A CAPTCHA generally involves one computer (often a server) asking a user to complete a test. While the computer program may be able to generate and grade the test, computer programs are generally not able to solve such a test on its own. Because computer programs are generally unable to solve a CAPTCHA, any user entering a correct solution may be presumed to be human. However, a CAPTCHA need not be such that computers can never solve them at all. Because a CAPTCHA is generally administered by a computer, in contrast to the standard Turing test that is administered by a human, a CAPTCHA is sometimes described as a reverse Turing test. Additional requirements for a test to be called a CAPTCHA may include: (1) test generation code and data should be public; and (2) the test should automatically be generated and graded by a machine. Ideally, although not always the case, a CAPTCHA test would be such that an average computer user has no difficulty in passing it, and feels at ease while going through the test.
The use of CAPTCHAs in web interfaces, it is hoped will keep such Bots from misusing the web service. Human users will be easily able to authenticate themselves as being human by passing the tests while machines will typically fail. Some practical examples of web services where CAPTCHAs are required are: online polls, preventing spammers from getting free e-mail ids, preventing chat bots from irritating people in chat rooms, preventing automated online dictionary attacks in password systems, preventing unruly search engine bots from indexing private web pages, preventing web bots from adding advertisements to comment fields in Blogs etc. As the web replaces human to human physical interaction such examples are bound to increase.
A common type of CAPTCHA requires that the user type the letters of a distorted image, sometimes with the addition of an obscured sequence of letters or digits that appears on the screen. A person's ability to pass this CAPTCHA may be related to the person's familiarity with the language that the letters or digits originate. Many of these CAPTCHAs currently in use are English word based CAPTCHAs. The English word based CAPTCHAs irrespective of whether they use or do not use dictionary words, make the assumption that the test taker is familiar with English letters. This might not be true for international users of international web service providers, (e.g. Yahoo). Word based CAPTCHAs present a distorted image of a word composed of English letters to the user. The human user is able to apply error correction to the image to decipher the word while a machine is at a loss to know the word. The machine based OCR systems have not advanced so much as to reach the level of the error correction that a human can perform on distorted letters.
There are a few image based CAPTCHAs. The human face image based scheme “Artifacial,” makes use of the fact that a human can quickly detect a human face in an image with a highly cluttered background. (See Y. Rui and Z. Liu. Artifacial: automated reverse turing test using facial features. In MULTIMEDIA '03: Proceedings of the eleventh ACM international conference on Multimedia, pages 295-298, New York, N.Y., USA, 2003. ACM Press). This CAPTCHA is merely a human face detection problem and requires a user to identify a particular location within an image.
‘Implicit CAPTCHAs’ make use of images in a much more general way. (See H. S. Baird and J. L. Bentley. Implicit captchas. In Proceedings of SPIE/IS&T Conference on Document Recognition and Retrieval XII, 2005). The user is supposed to interact with the picture by clicking on some part of it and thus pass the test. The image in this scheme provides the background for the test, upon which an interaction based task is built. This type of CAPTCHA is an object detection problem and requires a user to identify a particular location within an image.
In the scheme “Image Recognition CAPTCHAs,” the hardness of the problem is provided by the one way transformation between words and pictures. (See M. Chew and J. D. Tygar. Image recognition captchas. In ISC, pages 268-279, 2004). For a machine, it is easy to get pictures corresponding to a particular chosen word, but tough, the other way around. Thus given pictures associated with a word, the human can easily find the word while the machine will fail. This scheme plays around with a few possibilities of this mapping between words and their associated pictures. This is a complicated scheme that requires a user to match a cultural term with a image of an object.
What is a good CAPTCHA test today may break in the years to come. Such a CAPTCHA test will also be a good test. What is needed is a culturally universal CAPTCHA that a human can pass, independently of the person's familiarity with any particular language or culture and that a computer will have difficulty passing for the foreseeable future.